package com.xucia.jsponic.data;

import java.util.Arrays;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.RandomAccess;
import java.util.Set;

import org.mozilla.javascript.NativeArray;
import org.mozilla.javascript.Scriptable;

import com.xucia.jsponic.datasource.IndexedListDataSource;
import com.xucia.jsponic.datasource.WritableDataSource;

public abstract class PersistentList extends PersistableImpl implements List,PersistableList {
	public abstract long getLength();
	protected abstract void initializeArray(Object[] array);
	public Set<String> keySet() { // an array should not include the integers
		Object[] ids = getIds();
		Set<String> keySet = new HashSet();
		for (Object id : ids)
			if (id instanceof String)
				keySet.add((String) id);
		return keySet;
	}
	protected void recordPut(int index, Object value) {
		enforceType("items", value, true, true);
    	if (index == getLength())
    		checkAppendSecurity();
    	else
    		checkWriteSecurity(this);
       	try {
    		Identification id = getId();
    		if (id.source != null) { 
		    	if (id.source instanceof IndexedListDataSource && index != getLength())
		    		((IndexedListDataSource) id.source).recordListReplace(id.subObjectId, index, convertToIdIfNeeded(value));
		    	else {
		    		((WritableDataSource) id.source).recordListAdd(id.subObjectId, convertToIdIfNeeded(value));
		    	}
    		}
		} catch (Exception e) {
			throw new RuntimeException(e);
		}
		firePropertyChange("" + index,value);

	}

	public boolean add(Object value) {
		put(size(), this, value);
/*		if (isPersistingList) {
			DataObject historyEntry = newHistoryEntry();
			if (historyEntry != null)
				historyEntry.set(GlobalData.BASIS_FIELD,convertToIdIfNeeded(Templates.findTemplate("historyAppend")));
		}*/
     	return true;
    }

    public void add(int index, Object element) {
        /*   if (data == null) 
               data = new TransientDataObjectList();*/
    	enforceType("items", element, true, true);
    	Object oldValue = get(index);
    	if (id != null && id.source != null) {
	       	checkWriteSecurity(this);
	       	try {
	    		Identification id = getId();
	    		if (id.source != null) { 
/*			    	if (id.source instanceof IndexedListDataSource)
			    		//((IndexedListDataSource) id.source).recordListAdd(id.objectId, index, convertToIdIfNeeded(element));
			    	else*/
	    			((WritableDataSource) id.source).recordListAdd(id.subObjectId, convertToIdIfNeeded(element));
	    		}
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
			firePropertyChange("" + index,element);
    	}
    	boolean middle = index != size();
    	put(index,this,element);
    	if (middle)
    		add(index+1,oldValue);
   }
    public Object set(int index, Object element) {
    	put(index,this,element);
    	return element;
    }
   /* @Override
	public void put(int index, Scriptable start, Object value)
    {
    	if (isPersistingList && !isModifying) {
    		int size = size();
        	if (index == size)
        		checkAppendSecurity();
        	else
        		checkWriteSecurity(this);
	       	try {
	    		Identification id = getId();
	    		if (id.source != null) { 
			    	if (id.source instanceof IndexedListDataSource && index != size)
			    		((IndexedListDataSource) id.source).recordListReplace(id.objectId, index, convertToIdIfNeeded(value));
			    	else {
			    		if (index != size)
			    			delete(index);
			    		id.source.recordListAdd(id.objectId, convertToIdIfNeeded(value));
			    	}
	    		}
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
    	}
   		super.put(index, start, value);
    }*/


    public boolean remove(Object o) {
    	int index = indexOf(o);
    	if (index == -1)
    		return false;
    	//TODO: Must set this directly, this is terribly inefficient
    	NativeArray.splice(this, new Object[]{index,1});
    	return true;
    }
    /*protected boolean addFromSourceIterator() {
    	if (iterator.hasNext()) {
    		super.put((int) ((NativeArray)this).getLength(), this, iterator.next());
    		return true;
    	}
    	return false;
    }*/
/*	@Override
	public Object get(int index, Scriptable start) {
		
		Object value;
		do {
			value = super.get(index,this);
		}
		while (value == Scriptable.NOT_FOUND && addFromSourceIterator()); 
        return value;
    }
    */ 
     
     
    public int size() {
    	return (int) getLength();
	}
	@Override
	public String getClassName() {
		return "PersistentList";
	}
/*	public static PersistentList filter(List superList, Stipulation stipulation) {
		QueryId filterObjectId = QueryId.idForObject(((PersistentList)superList).id.source, ((PersistentList)superList).id.subObjectId, stipulation);
		return (PersistentList) filterObjectId.getTarget();
	}
	Iterator iterator;
	public Stipulation getStipulation() {
		if (id instanceof QueryId)
			return ((QueryId)id).stipulation;
		else
			return null;
	}*/
	/* From AbstractCollection */
    /**
     * {@inheritDoc}
     *
     * <p>This implementation returns <tt>size() == 0</tt>.
     */
    public boolean isEmpty() {
	return size() == 0;
    }

    /**
     * {@inheritDoc}
     *
     * <p>This implementation iterates over the elements in the collection,
     * checking each element in turn for equality with the specified element.
     *
     * @throws ClassCastException   {@inheritDoc}
     * @throws NullPointerException {@inheritDoc}
     */
    public boolean contains(Object o) {
	Iterator e = iterator();
	if (o==null) {
	    while (e.hasNext())
		if (e.next()==null)
		    return true;
	} else {
	    while (e.hasNext())
		if (o.equals(e.next()))
		    return true;
	}
	return false;
    }

    /**
     * {@inheritDoc}
     *
     * <p>This implementation returns an array containing all the elements
     * returned by this collection's iterator, in the same order, stored in
     * consecutive elements of the array, starting with index {@code 0}.
     * The length of the returned array is equal to the number of elements
     * returned by the iterator, even if the size of this collection changes
     * during iteration, as might happen if the collection permits
     * concurrent modification during iteration.  The {@code size} method is
     * called only as an optimization hint; the correct result is returned
     * even if the iterator returns a different number of elements.
     *
     * <p>This method is equivalent to:
     *
     *  <pre> {@code
     * List list = new ArrayList(size());
     * for (E e : this)
     *     list.add(e);
     * return list.toArray();
     * }</pre>
     */
    public Object[] toArray() {
        // Estimate size of array; be prepared to see more or fewer elements
	Object[] r = new Object[size()];
        Iterator it = iterator();
	for (int i = 0; i < r.length; i++) {
	    if (! it.hasNext())	// fewer elements than expected
		return Arrays.copyOf(r, i);
	    r[i] = it.next();
	}
	return it.hasNext() ? finishToArray(r, it) : r;
    }

    /**
     * {@inheritDoc}
     *
     * <p>This implementation returns an array containing all the elements
     * returned by this collection's iterator in the same order, stored in
     * consecutive elements of the array, starting with index {@code 0}.
     * If the number of elements returned by the iterator is too large to
     * fit into the specified array, then the elements are returned in a
     * newly allocated array with length equal to the number of elements
     * returned by the iterator, even if the size of this collection
     * changes during iteration, as might happen if the collection permits
     * concurrent modification during iteration.  The {@code size} method is
     * called only as an optimization hint; the correct result is returned
     * even if the iterator returns a different number of elements.
     *
     * <p>This method is equivalent to:
     *
     *  <pre> {@code
     * List list = new ArrayList(size());
     * for (E e : this)
     *     list.add(e);
     * return list.toArray(a);
     * }</pre>
     *
     * @throws ArrayStoreException  {@inheritDoc}
     * @throws NullPointerException {@inheritDoc}
     */
    public Object[] toArray(Object[] a) {
        // Estimate size of array; be prepared to see more or fewer elements
        int size = size();
        Object[] r = a.length >= size ? a :
                  (Object[])java.lang.reflect.Array
                  .newInstance(a.getClass().getComponentType(), size);
        Iterator it = iterator();

	for (int i = 0; i < r.length; i++) {
	    if (! it.hasNext()) { // fewer elements than expected
		if (a != r)
		    return Arrays.copyOf(r, i);
		r[i] = null; // null-terminate
		return r;
	    }
	    r[i] = it.next();
	}
	return it.hasNext() ? finishToArray(r, it) : r;
    }

    /**
     * Reallocates the array being used within toArray when the iterator
     * returned more elements than expected, and finishes filling it from
     * the iterator.
     *
     * @param r the array, replete with previously stored elements
     * @param it the in-progress iterator over this collection
     * @return array containing the elements in the given array, plus any
     *         further elements returned by the iterator, trimmed to size
     */
    private static  Object[] finishToArray(Object[] r, Iterator<?> it) {
	int i = r.length;
        while (it.hasNext()) {
            int cap = r.length;
            if (i == cap) {
                int newCap = ((cap / 2) + 1) * 3;
                if (newCap <= cap) { // integer overflow
		    if (cap == Integer.MAX_VALUE)
			throw new OutOfMemoryError
			    ("Required array size too large");
		    newCap = Integer.MAX_VALUE;
		}
		r = Arrays.copyOf(r, newCap);
	    }
	    r[i++] = it.next();
        }
        // trim if overallocated
        return (i == r.length) ? r : Arrays.copyOf(r, i);
    }

    // Bulk Operations

    /**
     * {@inheritDoc}
     *
     * <p>This implementation iterates over the specified collection,
     * checking each element returned by the iterator in turn to see
     * if it's contained in this collection.  If all elements are so
     * contained <tt>true</tt> is returned, otherwise <tt>false</tt>.
     *
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @see #contains(Object)
     */
    public boolean containsAll(Collection c) {
	Iterator<?> e = c.iterator();
	while (e.hasNext())
	    if (!contains(e.next()))
		return false;
	return true;
    }

    /**
     * {@inheritDoc}
     *
     * <p>This implementation iterates over the specified collection, and adds
     * each object returned by the iterator to this collection, in turn.
     *
     * <p>Note that this implementation will throw an
     * <tt>UnsupportedOperationException</tt> unless <tt>add</tt> is
     * overridden (assuming the specified collection is non-empty).
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     * @throws IllegalStateException         {@inheritDoc}
     *
     * @see #add(Object)
     */
    public boolean addAll(Collection c) {
	boolean modified = false;
	Iterator e = c.iterator();
	while (e.hasNext()) {
	    if (add(e.next()))
		modified = true;
	}
	return modified;
    }

    /**
     * {@inheritDoc}
     *
     * <p>This implementation iterates over this collection, checking each
     * element returned by the iterator in turn to see if it's contained
     * in the specified collection.  If it's so contained, it's removed from
     * this collection with the iterator's <tt>remove</tt> method.
     *
     * <p>Note that this implementation will throw an
     * <tt>UnsupportedOperationException</tt> if the iterator returned by the
     * <tt>iterator</tt> method does not implement the <tt>remove</tt> method
     * and this collection contains one or more elements in common with the
     * specified collection.
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     *
     * @see #remove(Object)
     * @see #contains(Object)
     */
    public boolean removeAll(Collection c) {
	boolean modified = false;
	Iterator<?> e = iterator();
	while (e.hasNext()) {
	    if (c.contains(e.next())) {
		e.remove();
		modified = true;
	    }
	}
	return modified;
    }

    /**
     * {@inheritDoc}
     *
     * <p>This implementation iterates over this collection, checking each
     * element returned by the iterator in turn to see if it's contained
     * in the specified collection.  If it's not so contained, it's removed
     * from this collection with the iterator's <tt>remove</tt> method.
     *
     * <p>Note that this implementation will throw an
     * <tt>UnsupportedOperationException</tt> if the iterator returned by the
     * <tt>iterator</tt> method does not implement the <tt>remove</tt> method
     * and this collection contains one or more elements not present in the
     * specified collection.
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     *
     * @see #remove(Object)
     * @see #contains(Object)
     */
    public boolean retainAll(Collection c) {
	boolean modified = false;
	Iterator e = iterator();
	while (e.hasNext()) {
	    if (!c.contains(e.next())) {
		e.remove();
		modified = true;
	    }
	}
	return modified;
    }


     
     /* From AbstractList */





     // Search Operations

     /**
      * {@inheritDoc}
      *
      * <p>This implementation first gets a list iterator (with
      * {@code listIterator()}).  Then, it iterates over the list until the
      * specified element is found or the end of the list is reached.
      *
      * @throws ClassCastException   {@inheritDoc}
      * @throws NullPointerException {@inheritDoc}
      */
     public int indexOf(Object o) {
 	ListIterator e = listIterator();
 	if (o==null) {
 	    while (e.hasNext())
 		if (e.next()==null)
 		    return e.previousIndex();
 	} else {
 	    while (e.hasNext())
 		if (o.equals(e.next()))
 		    return e.previousIndex();
 	}
 	return -1;
     }

     /**
      * {@inheritDoc}
      *
      * <p>This implementation first gets a list iterator that points to the end
      * of the list (with {@code listIterator(size())}).  Then, it iterates
      * backwards over the list until the specified element is found, or the
      * beginning of the list is reached.
      *
      * @throws ClassCastException   {@inheritDoc}
      * @throws NullPointerException {@inheritDoc}
      */
     public int lastIndexOf(Object o) {
 	ListIterator e = listIterator(size());
 	if (o==null) {
 	    while (e.hasPrevious())
 		if (e.previous()==null)
 		    return e.nextIndex();
 	} else {
 	    while (e.hasPrevious())
 		if (o.equals(e.previous()))
 		    return e.nextIndex();
 	}
 	return -1;
     }


     // Bulk Operations

     /**
      * Removes all of the elements from this list (optional operation).
      * The list will be empty after this call returns.
      *
      * <p>This implementation calls {@code removeRange(0, size())}.
      *
      * <p>Note that this implementation throws an
      * {@code UnsupportedOperationException} unless {@code remove(int
      * index)} or {@code removeRange(int fromIndex, int toIndex)} is
      * overridden.
      *
      * @throws UnsupportedOperationException if the {@code clear} operation
      *         is not supported by this list
      */
     public void clear() {
         removeRange(0, size());
     }

     /**
      * {@inheritDoc}
      *
      * <p>This implementation gets an iterator over the specified collection
      * and iterates over it, inserting the elements obtained from the
      * iterator into this list at the appropriate position, one at a time,
      * using {@code add(int, E)}.
      * Many implementations will override this method for efficiency.
      *
      * <p>Note that this implementation throws an
      * {@code UnsupportedOperationException} unless
      * {@link #add(int, Object) add(int, E)} is overridden.
      *
      * @throws UnsupportedOperationException {@inheritDoc}
      * @throws ClassCastException            {@inheritDoc}
      * @throws NullPointerException          {@inheritDoc}
      * @throws IllegalArgumentException      {@inheritDoc}
      * @throws IndexOutOfBoundsException     {@inheritDoc}
      */
     public boolean addAll(int index, Collection c) {
 	boolean modified = false;
 	Iterator e = c.iterator();
 	while (e.hasNext()) {
 	    add(index++, e.next());
 	    modified = true;
 	}
 	return modified;
     }


     // Iterators

     /**
      * Returns an iterator over the elements in this list in proper sequence.
      *
      * <p>This implementation returns a straightforward implementation of the
      * iterator interface, relying on the backing list's {@code size()},
      * {@code get(int)}, and {@code remove(int)} methods.
      *
      * <p>Note that the iterator returned by this method will throw an
      * {@code UnsupportedOperationException} in response to its
      * {@code remove} method unless the list's {@code remove(int)} method is
      * overridden.
      *
      * <p>This implementation can be made to throw runtime exceptions in the
      * face of concurrent modification, as described in the specification
      * for the (protected) {@code modCount} field.
      *
      * @return an iterator over the elements in this list in proper sequence
      *
      * @see #modCount
      */
     public Iterator iterator() {
 	return new Itr();
     }

     /**
      * {@inheritDoc}
      *
      * <p>This implementation returns {@code listIterator(0)}.
      *
      * @see #listIterator(int)
      */
     public ListIterator listIterator() {
 	return listIterator(0);
     }

     /**
      * {@inheritDoc}
      *
      * <p>This implementation returns a straightforward implementation of the
      * {@code ListIterator} interface that extends the implementation of the
      * {@code Iterator} interface returned by the {@code iterator()} method.
      * The {@code ListIterator} implementation relies on the backing list's
      * {@code get(int)}, {@code set(int, E)}, {@code add(int, E)}
      * and {@code remove(int)} methods.
      *
      * <p>Note that the list iterator returned by this implementation will
      * throw an {@code UnsupportedOperationException} in response to its
      * {@code remove}, {@code set} and {@code add} methods unless the
      * list's {@code remove(int)}, {@code set(int, E)}, and
      * {@code add(int, E)} methods are overridden.
      *
      * <p>This implementation can be made to throw runtime exceptions in the
      * face of concurrent modification, as described in the specification for
      * the (protected) {@code modCount} field.
      *
      * @throws IndexOutOfBoundsException {@inheritDoc}
      *
      * @see #modCount
      */
     public ListIterator listIterator(final int index) {
 	if (index<0 || index>size())
 	  throw new IndexOutOfBoundsException("Index: "+index);

 	return new ListItr(index);
     }

     private class Itr implements Iterator {
 	/**
 	 * Index of element to be returned by subsequent call to next.
 	 */
 	int cursor = 0;

 	/**
 	 * Index of element returned by most recent call to next or
 	 * previous.  Reset to -1 if this element is deleted by a call
 	 * to remove.
 	 */
 	int lastRet = -1;

 	/**
 	 * The modCount value that the iterator believes that the backing
 	 * List should have.  If this expectation is violated, the iterator
 	 * has detected concurrent modification.
 	 */
 	int expectedModCount = modCount;

 	public boolean hasNext() {
             return cursor != size();
 	}

 	public Object next() {
             checkForComodification();
 	    try {
 		Object next = get(cursor);
 		lastRet = cursor++;
 		return next;
 	    } catch (IndexOutOfBoundsException e) {
 		checkForComodification();
 		throw new NoSuchElementException();
 	    }
 	}

 	public void remove() {
 	    if (lastRet == -1)
 		throw new IllegalStateException();
             checkForComodification();

 	    try {
 		PersistentList.this.remove(lastRet);
 		if (lastRet < cursor)
 		    cursor--;
 		lastRet = -1;
 		expectedModCount = modCount;
 	    } catch (IndexOutOfBoundsException e) {
 		throw new ConcurrentModificationException();
 	    }
 	}

 	final void checkForComodification() {
 	    if (modCount != expectedModCount)
 		throw new ConcurrentModificationException();
 	}
     }

     private class ListItr extends Itr implements ListIterator {
 	ListItr(int index) {
 	    cursor = index;
 	}

 	public boolean hasPrevious() {
 	    return cursor != 0;
 	}

         public Object previous() {
             checkForComodification();
             try {
                 int i = cursor - 1;
                 Object previous = get(i);
                 lastRet = cursor = i;
                 return previous;
             } catch (IndexOutOfBoundsException e) {
                 checkForComodification();
                 throw new NoSuchElementException();
             }
         }

 	public int nextIndex() {
 	    return cursor;
 	}

 	public int previousIndex() {
 	    return cursor-1;
 	}

 	public void set(Object e) {
 	    if (lastRet == -1)
 		throw new IllegalStateException();
             checkForComodification();

 	    try {
 		PersistentList.this.set(lastRet, e);
 		expectedModCount = modCount;
 	    } catch (IndexOutOfBoundsException ex) {
 		throw new ConcurrentModificationException();
 	    }
 	}

 	public void add(Object e) {
             checkForComodification();

 	    try {
 		PersistentList.this.add(cursor++, e);
 		lastRet = -1;
 		expectedModCount = modCount;
 	    } catch (IndexOutOfBoundsException ex) {
 		throw new ConcurrentModificationException();
 	    }
 	}
     }

     /**
      * {@inheritDoc}
      *
      * <p>This implementation returns a list that subclasses
      * {@code PersistentList}.  The subclass stores, in private fields, the
      * offset of the subList within the backing list, the size of the subList
      * (which can change over its lifetime), and the expected
      * {@code modCount} value of the backing list.  There are two variants
      * of the subclass, one of which implements {@code RandomAccess}.
      * If this list implements {@code RandomAccess} the returned list will
      * be an instance of the subclass that implements {@code RandomAccess}.
      *
      * <p>The subclass's {@code set(int, E)}, {@code get(int)},
      * {@code add(int, E)}, {@code remove(int)}, {@code addAll(int,
      * Collection)} and {@code removeRange(int, int)} methods all
      * delegate to the corresponding methods on the backing abstract list,
      * after bounds-checking the index and adjusting for the offset.  The
      * {@code addAll(Collection c)} method merely returns {@code addAll(size,
      * c)}.
      *
      * <p>The {@code listIterator(int)} method returns a "wrapper object"
      * over a list iterator on the backing list, which is created with the
      * corresponding method on the backing list.  The {@code iterator} method
      * merely returns {@code listIterator()}, and the {@code size} method
      * merely returns the subclass's {@code size} field.
      *
      * <p>All methods first check to see if the actual {@code modCount} of
      * the backing list is equal to its expected value, and throw a
      * {@code ConcurrentModificationException} if it is not.
      *
      * @throws IndexOutOfBoundsException endpoint index value out of range
      *         {@code (fromIndex < 0 || toIndex > size)}
      * @throws IllegalArgumentException if the endpoint indices are out of order
      *         {@code (fromIndex > toIndex)}
      */
     public List subList(int fromIndex, int toIndex) {
         return (this instanceof RandomAccess ?
                 new RandomAccessSubList(this, fromIndex, toIndex) :
                 new SubList(this, fromIndex, toIndex));
     }

     /**
      * Removes from this list all of the elements whose index is between
      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
      * Shifts any succeeding elements to the left (reduces their index).
      * This call shortens the ArrayList by {@code (toIndex - fromIndex)}
      * elements.  (If {@code toIndex==fromIndex}, this operation has no
      * effect.)
      *
      * <p>This method is called by the {@code clear} operation on this list
      * and its subLists.  Overriding this method to take advantage of
      * the internals of the list implementation can <i>substantially</i>
      * improve the performance of the {@code clear} operation on this list
      * and its subLists.
      *
      * <p>This implementation gets a list iterator positioned before
      * {@code fromIndex}, and repeatedly calls {@code ListIterator.next}
      * followed by {@code ListIterator.remove} until the entire range has
      * been removed.  <b>Note: if {@code ListIterator.remove} requires linear
      * time, this implementation requires quadratic time.</b>
      *
      * @param fromIndex index of first element to be removed
      * @param toIndex index after last element to be removed
      */
     protected void removeRange(int fromIndex, int toIndex) {
         ListIterator it = listIterator(fromIndex);
         for (int i=0, n=toIndex-fromIndex; i<n; i++) {
             it.next();
             it.remove();
         }
     }

     /**
      * The number of times this list has been <i>structurally modified</i>.
      * Structural modifications are those that change the size of the
      * list, or otherwise perturb it in such a fashion that iterations in
      * progress may yield incorrect results.
      *
      * <p>This field is used by the iterator and list iterator implementation
      * returned by the {@code iterator} and {@code listIterator} methods.
      * If the value of this field changes unexpectedly, the iterator (or list
      * iterator) will throw a {@code ConcurrentModificationException} in
      * response to the {@code next}, {@code remove}, {@code previous},
      * {@code set} or {@code add} operations.  This provides
      * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
      * the face of concurrent modification during iteration.
      *
      * <p><b>Use of this field by subclasses is optional.</b> If a subclass
      * wishes to provide fail-fast iterators (and list iterators), then it
      * merely has to increment this field in its {@code add(int, E)} and
      * {@code remove(int)} methods (and any other methods that it overrides
      * that result in structural modifications to the list).  A single call to
      * {@code add(int, E)} or {@code remove(int)} must add no more than
      * one to this field, or the iterators (and list iterators) will throw
      * bogus {@code ConcurrentModificationExceptions}.  If an implementation
      * does not wish to provide fail-fast iterators, this field may be
      * ignored.
      */
     protected transient int modCount = 0;
 }

 class SubList extends PersistentList {

	private PersistentList l;
     private int offset;
     private int size;
     private int expectedModCount;
     @Override
 	public long getLength() {
 		return size;
 	}
 	protected void initializeArray(Object[] array) {
		throw new UnsupportedOperationException();
	}

     SubList(PersistentList list, int fromIndex, int toIndex) {
         if (fromIndex < 0)
             throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
         if (toIndex > list.size())
             throw new IndexOutOfBoundsException("toIndex = " + toIndex);
         if (fromIndex > toIndex)
             throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                                ") > toIndex(" + toIndex + ")");
         l = list;
         offset = fromIndex;
         size = toIndex - fromIndex;
         expectedModCount = l.modCount;
     }

     public Object set(int index, Object element) {
         rangeCheck(index);
         checkForComodification();
         return l.set(index+offset, element);
     }

     public Object get(int index) {
         rangeCheck(index);
         checkForComodification();
         return l.get(index+offset);
     }

     public int size() {
         checkForComodification();
         return size;
     }

     public void add(int index, Object element) {
         if (index<0 || index>size)
             throw new IndexOutOfBoundsException();
         checkForComodification();
         l.add(index+offset, element);
         expectedModCount = l.modCount;
         size++;
         modCount++;
     }

     public Object remove(int index) {
         rangeCheck(index);
         checkForComodification();
         Object result = l.remove(index+offset);
         expectedModCount = l.modCount;
         size--;
         modCount++;
         return result;
     }

     protected void removeRange(int fromIndex, int toIndex) {
         checkForComodification();
         l.removeRange(fromIndex+offset, toIndex+offset);
         expectedModCount = l.modCount;
         size -= (toIndex-fromIndex);
         modCount++;
     }

     public boolean addAll(Collection c) {
         return addAll(size, c);
     }

     public boolean addAll(int index, Collection c) {
         if (index<0 || index>size)
             throw new IndexOutOfBoundsException(
                 "Index: "+index+", Size: "+size);
         int cSize = c.size();
         if (cSize==0)
             return false;

         checkForComodification();
         l.addAll(offset+index, c);
         expectedModCount = l.modCount;
         size += cSize;
         modCount++;
         return true;
     }

     public Iterator iterator() {
         return listIterator();
     }

     public ListIterator listIterator(final int index) {
         checkForComodification();
         if (index<0 || index>size)
             throw new IndexOutOfBoundsException(
                 "Index: "+index+", Size: "+size);

         return new ListIterator() {
             private ListIterator i = l.listIterator(index+offset);

             public boolean hasNext() {
                 return nextIndex() < size;
             }

             public Object next() {
                 if (hasNext())
                     return i.next();
                 else
                     throw new NoSuchElementException();
             }

             public boolean hasPrevious() {
                 return previousIndex() >= 0;
             }

             public Object previous() {
                 if (hasPrevious())
                     return i.previous();
                 else
                     throw new NoSuchElementException();
             }

             public int nextIndex() {
                 return i.nextIndex() - offset;
             }

             public int previousIndex() {
                 return i.previousIndex() - offset;
             }

             public void remove() {
                 i.remove();
                 expectedModCount = l.modCount;
                 size--;
                 modCount++;
             }

             public void set(Object e) {
                 i.set(e);
             }

             public void add(Object e) {
                 i.add(e);
                 expectedModCount = l.modCount;
                 size++;
                 modCount++;
             }
         };
     }

     public List subList(int fromIndex, int toIndex) {
         return new SubList(this, fromIndex, toIndex);
     }

     private void rangeCheck(int index) {
         if (index<0 || index>=size)
             throw new IndexOutOfBoundsException("Index: "+index+
                                                 ",Size: "+size);
     }

     private void checkForComodification() {
         if (l.modCount != expectedModCount)
             throw new ConcurrentModificationException();
     }
 }

 class RandomAccessSubList extends SubList implements RandomAccess {
     RandomAccessSubList(PersistentList list, int fromIndex, int toIndex) {
         super(list, fromIndex, toIndex);
     }

     public List subList(int fromIndex, int toIndex) {
         return new RandomAccessSubList(this, fromIndex, toIndex);
     }
 }

